//027. 二次质数
//        欧拉发现了著名的二次公式：n^2 + n + 41，发现这个公式可以对于 0≤n≤39 的整数可以连
//        续产生四十个素数。
//        但是，当 n=40, 40^2 + 40 + 41 = 40(40+1)+41 可以被 41 整除；
//        当 n=41, 41^2 + 41 + 41 显然也可以被 41 整除。
//        另外一个著名公式是  n^2 − 79n + 1601，可以对 0≤n≤79 的整数连续产生 80 个素数，这个
//        公式的两个系数 −79 和 1601 的乘积是−126479。
//        考虑如下二次公式： n^2 + an + b,其中,|a|<1000 and |b|<1000
//        求使得以上公式从 n=0 开始连续产生的素数最多的系数 a 与 b 的乘积。
//        答案：-59231 (最长的是 71 个连续的素数 0≤n≤70 此时 a=-61 b=971)

public class Week027 {
    static final int N = 1000;

    public static boolean isPrime(int n) {
        if (n <= 3) return n > 1;
        if (n % 6 != 1 && n % 6 != 5) return false;
        int n_s = (int) Math.sqrt(n);
        for (int i = 5; i <= n_s; i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }

    static int getPrimeLength(int a, int b) {
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            if (!isPrime(i * i + a * i + b)) return ans;
            ++ans;
        }
        return ans;
    }

    static void run() {
        int ansN = 0, ans = 0;
        int start = 1 - N, end = N - 1;
        for (int a = start; a <= end; ++a) {
            for (int b = start; b <= end; ++b) {
                int t = getPrimeLength(a, b);
                if (t > ansN) {
                    ansN = t;
                    ans = a * b;
                }
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}